package dp.leetcode_322;

import java.util.HashMap;

public class MemoRecur {
    public int coinChange(int[] coins, int amount) {
        // K：金额， V：凑成该 Key 所需的方案数
        HashMap<Integer, Integer> memo = new HashMap<>();
        return findWays(coins, amount, memo);
    }
    public int findWays(int[] coins, int amount, HashMap<Integer, Integer> memo) {
        if (memo.containsKey(amount)) {
            return memo.get(amount);
        }
        if (amount < 0) {
            return -1;
        }
        if (amount == 0) {
            return 0;
        }
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < coins.length; i++) {
            int ways = findWays(coins, amount - coins[i], memo);
            if (ways == -1) {
                continue;
            }
            res = Math.min(res, ways + 1);
        }
        res = res == Integer.MAX_VALUE ? -1 : res;
        memo.put(amount, res);
        return res;
    }
}
